package swordoffer.offer8;

public class GetNext {
    public static void main(String[] args) {
        TreeLinkNode head = new TreeLinkNode(6);
        head.next = null;
        head.left = new TreeLinkNode(3);
        head.right = new TreeLinkNode(101);
        head.left.next = head;
        head.left.left = new TreeLinkNode(1);
        head.left.left.next = head.left;
        head.left.left.right = new TreeLinkNode(2);
        head.left.left.right.next = head.left.left;
        GetNext(head.left.left);
    }
    public static TreeLinkNode GetNext(TreeLinkNode pNode) {
        if(pNode == null){
            return null;
        }
        //右树存在，右树的最左节点就是后继节点
        if(pNode.right != null){
            return getMostLeft(pNode.right);
        }else {//右树不存在
            TreeLinkNode parent = pNode.next;
            while (parent != null && parent.right == pNode){
                pNode = parent;
                parent = pNode.next;
            }
            return parent;
        }
    }
    public static TreeLinkNode getMostLeft(TreeLinkNode node){
        while (node.left != null){
            node = node.left;
        }
        return node;
    }
}
